package com.aurora.leetcode.sort;

import com.aurora.leetcode.util.MyUtils;

/**
 * @author : Aurora
 * @date : 2024/5/7 11:32
 * @description 排序算法：堆排序
 */
public class HeapSort {
    public void heapSort(int[] elems){
        int n = elems.length;
        //构建初始大顶堆
        for(int i=n/2-1;i>=0;--i){
            adjustHeap(elems,i,n-1);
        }
        //排序
        for(int i=n-1; i>=0; --i){
            //将当前最大值置于未排序数组末尾
            swap(elems, i, 0);
            //调整未排序数组
            adjustHeap(elems,0,i-1);
        }
    }

    public void adjustHeap(int[] elems, int parent, int n){
        int temp = elems[parent];
        int child = 2*parent+1;
        while(child <= n){
            if(child +1<=n && elems[child]<elems[child+1])
                child ++;
            if(elems[child] < temp) break;
            elems[parent] = elems[child];
            parent = child;
            child = 2*parent+1;
        }
        elems[parent] = temp;
    }
    public void swap(int[] elems, int ele1, int ele2){
        int temp = elems[ele1];
        elems[ele1] = elems[ele2];
        elems[ele2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,5,7,10,3,1,6,9,30,29,48,6};
        System.out.println("排序前的数组：");
        MyUtils.printArray(arr);
        System.out.println("排序后的数组：");
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);
        MyUtils.printArray(arr);
    }

}
